package com.origin.niuke.dynamic;

/**
 * 兑换零钱(二)
 * 给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额，请你计算并返回可以凑出总金额的的组合数。
 * 如果凑不出 target 则返回 0。
 * 输入：5,[1,2,4,5]   返回值：5
 * 算法：动态规划
 *
 * @author yezh
 * @date 2023/2/16 20:31
 */
public class NC203 {

    public int change(int target, int[] nums) {
        // write code here
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) for (int i = num; i <= target; i++) dp[i] += dp[i - num];
        return dp[target];
    }

}
